﻿// N皇后问题.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <chrono>
#include<iostream>
#define MAX 10000 //最多可能皇后数
#define swap(a,b) {int t = a; a = b; b = t;}

int row[MAX];
int col[MAX];

int N; 
int pdiag[2 * MAX];

int cdiag[2 * MAX];


int R[MAX];


int getP(int row, int col) {
    return row - col + N - 1;
}


int getC(int row, int col) {
    return row + col;
}


int my_rand(int begin, int end) {//左闭右开[begin, end)
    return rand() % (end - begin) + begin;
}


void randomize(int a[], int begin, int end)// 左闭右开
{
    for (int i = begin; i <= end - 2; i++) {
        int x = my_rand(i, end);
        swap(a[i], a[x]);
    }
}

void init()
{
    for (int i = 0; i < N; i++) {//N queens
        R[i] = i;
    }
    randomize(R, 0, N);//初始化N个皇后对应的R数组为0~N-1的一个排列，即没有任意皇后同列，也没有任何皇后同行
    for (int i = 0; i < N; i++) {
        row[i] = 1;//每行恰好一个皇后
        col[i] = 0;
    }
    for (int i = 0; i < 2 * N - 1; i++) {//N queens
        pdiag[i] = 0;
        cdiag[i] = 0;
    }
    for (int i = 0; i < N; i++) {//N queens
        col[R[i]]++;
        pdiag[getP(i, R[i])]++;
        cdiag[getC(i, R[i])]++;
    }
}

bool adjust_row(int row);
void print_result();
bool qualify();

int main(int argc, const char* argv[])
{
    srand((unsigned)time(NULL));
    scanf_s("%d", &N);
    auto start = std::chrono::high_resolution_clock::now();
    init();
    if (qualify()) {//运气很好，初始化后就满足终止条件
        print_result();
        return 0;
    }
    bool can_terminate = false;
    while (!can_terminate) {
        for (int i = 0; i < N; i++) {
            if (adjust_row(i)) {
                can_terminate = true;
                break;
            }
        }
    }
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> elapsed = end - start;
    std::cout << "Function execution time: " << elapsed.count() << " seconds" << std::endl;
    print_result();
    return 0;
}

bool adjust_row(int row) {
    int cur_col = R[row];
    int optimal_col = cur_col;//最佳列号，设置为当前列，然后更新
    int    min_conflict = col[optimal_col] + pdiag[getP(row, optimal_col)] - 1
        + cdiag[getC(row, optimal_col)] - 1;//对角线冲突数为当前对角线皇后数减一
    for (int i = 0; i < N; i++) {//逐个检查第row行的每个位置
        if (i == cur_col) {
            continue;
        }
        int conflict = col[i] + pdiag[getP(row, i)] + cdiag[getC(row, i)];
        if (conflict < min_conflict) {
            min_conflict = conflict;
            optimal_col = i;
        }
    }
    if (optimal_col != cur_col) {//要更新col,pdiag,cdiag
        col[cur_col]--;
        pdiag[getP(row, cur_col)]--;
        cdiag[getC(row, cur_col)]--;

        col[optimal_col]++;
        pdiag[getP(row, optimal_col)]++;
        cdiag[getC(row, optimal_col)]++;
        R[row] = optimal_col;
        if (col[cur_col] == 1 && col[optimal_col] == 1
            && pdiag[getP(row, optimal_col)] == 1 && cdiag[getC(row, optimal_col)] == 1) {
            return qualify();//qualify相对更耗时，所以只在满足上面基本条件后才检查
        }
    }
    //当前点就是最佳点，一切都保持不变
    return false;//如果都没变的话，肯定不满足终止条件，否则上一次就应该返回true并终止了
    //return qualify();
}
bool qualify() {
    for (int i = 0; i < N; i++) {//N queens
        if (col[R[i]] != 1 ||
            pdiag[getP(i, R[i])] != 1 ||
            cdiag[getC(i, R[i])] != 1) {
            return false;
        }
    }
    return true;
}
void print_result()
{
    printf("the result is like this:\n");
    for (int i = 0; i < N; i++) {
        printf("%d,", R[i]);
    }
    printf("\n");
    for (int j = 0; j < N; j++) {
        for (int k = 0; k < N; k++) {
            if (R[j] == k)
                printf("*");
            else
                printf("-");
        }
        printf("\n");
    }
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
